package greedy;

/**
 * @Author: 海琳琦
 * @Date: 2022/3/2 0:47
 * https://leetcode-cn.com/problems/binary-tree-cameras/
 */
public class MinCameraCover {

    static class TreeNode {
        int val;
        TreeNode left;
        TreeNode right;

        public TreeNode() {
        }

        public TreeNode(int val) {
            this.val = val;
        }

        public TreeNode(int val, TreeNode left, TreeNode right) {
            this.val = val;
            this.left = left;
            this.right = right;
        }
    }

    static int count;

    /**
     * 把摄像头放在叶子节点的父节点位置，才能充分利用摄像头的覆盖面积。
     * 所以我们要从下往上看，局部最优：让叶子节点的父节点安摄像头，所用摄像头最少，
     * 整体最优：全部摄像头数量所用最少！
     * @param root
     * @return
     */
    public static int minCameraCover(TreeNode root) {
        count = 0;
        if (traversal(root) == 0) {
            count++;
        }
        return count;
    }

    /**
     * 0:无覆盖 1:有覆盖 2：存放摄像头
     * @param root
     * @return
     */
    public static int traversal(TreeNode root) {
        //终止条件
        //如果是叶子结点看成有覆盖
        if (root == null) {
            return 1;
        }
        int left = traversal(root.left);
        int right = traversal(root.right);
        //孩子没覆盖，父节点有摄像头
        if (left == 0 || right == 0) {
            count++;
            return 2;
        }
        //孩子都有摄像头，父节点为覆盖
        if (left == 2 || right == 2) {
            return 1;
        }
        //孩子都有覆盖或孩子为空
        if (left == 1 && right == 1) {
            return 0;
        }
        return count;
    }

    public static void main(String[] args) {
        //[0,0,null,0,null,0,null,null,0]
        TreeNode root = new TreeNode(0);
        root.left = new TreeNode(0);
        root.left.left = new TreeNode(0);
        root.left.left.left = new TreeNode(0);
        root.left.left.left.right = new TreeNode(0);
        minCameraCover(root);
        System.out.println(count);
    }
}
